package com.wuyou.simple;

/**
 * 1539. 第 k 个缺失的正整数
 */
public class FindKthPositive {


    public static void main(String[] args) {
//        int[] arr = {2, 3, 4, 7, 11};
//        int k = 5;
//        int[] arr = {1,2,3,4};
//        int k = 2;
        int[] arr = {5,6,7,8,9};
        int k = 9;
        System.out.println(sol_1(arr, k));
    }

    /**
     * 暴力
     *
     * @param arr
     * @param k
     * @return
     */
    public static int sol_1(int[] arr, int k) {
        int misNum = arr[arr.length - 1] - arr.length;
        int[] missArr = new int[misNum];
        int misIndex = 0;

        int i = 0;
        int lastNum = 1;
        while (i < arr.length) {
            if (arr[i] != lastNum) {
                missArr[misIndex++] = lastNum++;
            } else {
                i++;
                lastNum++;
            }
        }
//        return misNum < k ? lastNum + k - 1 : missArr[k - 1];
        return missArr.length >= k ? missArr[k - 1] : lastNum + (k - missArr.length) - 1;
    }
}
